package 套娃信封问题;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @ClassName: EnvelopeNesting
 * @Description: TODO
 * @Author WN
 * @Date 2021/7/14 16:12
 * @Version V1.0
 */
public class EnvelopeNesting {
    public int maxEnvelopes(int[][] envelopes){
        int n=envelopes.length;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0];
            }
        });
        int [] height=new int[n];
        for (int i=0;i<n;i++){
            height[i]=envelopes[i][1];
        }
        return lengthOfLIS(height);
    }
    public int lengthOfLIS(int[] nums){
        int piles=0, n=nums.length;
        int[] top=new int[n];
        for (int i=0;i<n;i++){
            int poker=nums[i];
            int left=0,right=piles;
            while (left<right){
                int mid=(left+right)/2;
                if(top[mid]>=poker){
                    right=mid;
                }else {
                    left=mid+1;
                }
            }
            if (left==piles){
                piles++;
            }
            top[left]=poker;
        }
        return piles;
    }

}
